<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>День 5. Потоки.Base</h2>
<ol>
  <li>Базовые определения и свойства.</li>
  <ol>
    <li>Определение транспортной сети, потока, разреза, остаточной сети.</li>
    <li>Простейшие свойства потоков.</li>
  </ol></li>
  <li>Базовые алгоритмы.</li>
  <ol>
    <li>Алгоритм Форда-Фалкерсона нахождения максимального потока за O(f*E)</li>
    <li>Теорема Форда-Фалкерсона. Нахождение минимального разреза.</li>
    <li>Декомпозиция потока.</li>
  </ol></li>
  <li>Примеры задач решаемых нахождением максимального потока</li>
  <ol>
    <li>Нахождение максимального паросочетания за O(VE).</li>
    <li>Нахождение k реберно(вершинно)-непересекающихся путей в ориентированном(неориентированном) графе.</li>
    <li>Задача на Поток: даны суммы в строках и столбцах матрицы. Восстановить матрицу с такими суммами, чтобы все элементы были от 0 до 100.</li>
  </ol></li>
  <li>Алгоритмы нахождения максимального потока.</li>
  <ol>
    <li>Алгоритм Эдмондса-Карпа O(VE<sup>2</sup>) без доказательства</li>
    <li><span style="color: blue;">[на разборе]</span> Доказательство времени работы Эдмондса-Карпа</li>
    <li>Scaling O(E<sup>2</sup>log) с доказательством</li>
    <li>Пример, на котором Scaling работает долго O(E<sup>2</sup>log)</li>
    <li>Попытка улучшить Scaling до O(E<sup>2</sup>)</li>
  </ol></li>
  <li>mincost maxflow</li>
  <ol>
    <li>Поточная сеть с весами (w, -w, случай ориентированного и неориентированного графа)</li>
    <li>Алгоритм поиска mincost потока размера f, используя алгоритм Форда-Белмана за O(f*VE)</li>
    <li>Доказательство индукцией по f.</li>
    <li>Задачи на MinCost: у нас есть k автоматов, выполнить задание i --- занять делом один из автоматов в моменты времени [L<sub>i</sub>..R<sub>i</sub>], у каждого задания есть стоимость. Выполнить задания максимальной суммарной стоимости.</li>
  </ol></li>
  <li>Диниц</li>
  <ol>
    <li><span style="color: blue;">[на разборе]</span> Алгоритм Диница (сам алгоритм)</li>
    <li><span style="color: blue;">[на разборе]</span> Доказательство времени работы алгоритма Диница за O(V<sup>2</sup>E)</li>
    <li><span style="color: blue;">[на разборе]</span> Доказательство времени работы алгоритма Диница с масштабированием O(VElogM)</li>
  </ol></li>
</ol>
